//合并两个有序链表
//将两个升序链表合并为一个新的 升序 链表并返回。
//新链表是通过拼接给定的两个链表的所有节点组成的
#include<stdio.h>
#include<stdlib.h>


struct ListNode
{
	int val;
	struct ListNode* next;
};

void SLTNodePrintf(struct ListNode* ps)
{
	struct ListNode* cur = ps;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
//list1 和list2依次比较  取小的尾插
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	struct ListNode* newhead = NULL;
	struct ListNode* newheadtail = NULL;
	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;
	while ((list1 != NULL) && (list2 != NULL))
	{
		//小的尾插
		if (list1->val < list2->val)
		{
			//判断新结点是否为空
			if (newheadtail == NULL)
			{
				newhead = newheadtail = list1;
			}
			else
			{
				newheadtail->next = list1;
				newheadtail = newheadtail->next;
			}
			list1 = list1->next;
		}
		else
		{
			if (newheadtail == NULL)
			{
				newhead = newheadtail = list2;
			}
			else
			{
				newheadtail->next = list2;
				newheadtail = newheadtail->next;
			}
			list2 = list2->next;
		}
	}
	if (list1)
		newheadtail->next = list1;
	if (list2)
		newheadtail->next = list2;
	return newhead;
}




int main()
{
	struct ListNode* n1 = malloc(sizeof(struct ListNode));
	struct ListNode* n2 = malloc(sizeof(struct ListNode));
	struct ListNode* n3 = malloc(sizeof(struct ListNode));
	struct ListNode* n4 = malloc(sizeof(struct ListNode));
	struct ListNode* n5 = malloc(sizeof(struct ListNode));
	struct ListNode* n6 = malloc(sizeof(struct ListNode));

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;

	n4->val = 2;
	n5->val = 8;
	n6->val = 9;


	n1->next = n2;
	n2->next = n3;
	n3->next = NULL;

	n4->next = n5;
	n5->next = n6;
	n6->next = NULL;
	SLTNodePrintf(n1);

	struct ListNode* newnode = mergeTwoLists(n1, n4);
	SLTNodePrintf(newnode);

	return 0;
}